import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int left=1;
        int right=nums.length-1;
        Set<List<Integer>> list =new HashSet<>();

        int cur=0;
        while(cur<nums.length-1){

            if(cur!=0&&nums[cur]==nums[cur-1]){
                cur++;
                continue;
            }else{
                left=cur+1;
                right=nums.length-1;


                while(left<right){

                    if(nums[left]+nums[right]==-nums[cur]){
                        List<Integer> arr=new ArrayList();
                        arr.add(nums[cur]);
                        arr.add(nums[left]);
                        arr.add(nums[right]);
                        list.add(arr);
                        right--;
                        left++;

                    }else if(nums[left]+nums[right]>-nums[cur]){
                        right--;

                    }else{
                        left++;

                    }

                }


                cur++;
            }
        }

        return list.stream().toList();




    }

}






class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int left=1;
        int right=nums.length-1;
        List<List<Integer>> list=new ArrayList();

        int cur=0;
        while(cur<nums.length-1){

            if(cur!=0&&nums[cur]==nums[cur-1]){
                cur++;
                continue;
            }else{
                left=cur+1;
                right=nums.length-1;




                while(left<right){

                    if(nums[left]+nums[right]==-nums[cur]){
                        List<Integer> arr=new ArrayList();
                        arr.add(nums[cur]);
                        arr.add(nums[left]);
                        arr.add(nums[right]);
                        list.add(arr);
                        right--;
                        left++;

                        while(left<right&&nums[right]==nums[right+1]){
                            right--;

                        }

                        while(left<right&&nums[left-1]==nums[left]){
                            left++;

                        }


                    }else if(nums[left]+nums[right]>-nums[cur]){
                        right--;

                        while(left<right&&nums[right+1]==nums[right]){
                            right--;

                        }


                    }else{
                        left++;
                        while(left<right&&nums[left-1]==nums[left]){
                            left++;

                        }



                    }

                }


                cur++;
            }
        }

        return list;




    }

}
    